package com.wrial.simple;
/*
 * @Author  Wrial
 * @Date Created in 12:33 2020/3/29
 * @Description 给定有序nums创建高度最小的BST
 *
 * 那不就是使用最中间的元素作为根节点
 */

public class LeetCode_FaceTest04_02 {


    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        return bulidHelper(nums, 0, nums.length - 1);


    }

    private TreeNode bulidHelper(int[] nums, int left, int right) {
        if (left > right) return null;
        // 此处可以(left+right+1)/2都是BST，只不过是不同形式
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        //中间节点需要空出来
        node.left = bulidHelper(nums, left, mid - 1);
        node.right = bulidHelper(nums, mid+1, right);
        return node;

    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
